package main.剑指OfferⅠ;

import java.util.*;

public class Day28 {
    public static void main(String[] args) {//AC自动机
        System.out.println("剑指Offer37.序列化二叉树");
        System.out.println("剑指Offer38.字符串的排列");
    }
}

class Offer37{
    public String process1(TreeNode root, String str){//先序遍历
        if (root==null) return str+"#,";
        str+=String.valueOf(root.val)+",";
        str=process1(root.left,str);
        str=process1(root.right,str);
        return str;
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return process1(root,"");
    }

    public TreeNode process2(List<String> list){
        if (list.get(0).equals("#")) {
            list.remove(0);
            return null;
        }
        TreeNode curNode=new TreeNode(Integer.valueOf(list.get(0)));
        list.remove(0);
        curNode.left=process2(list);
        curNode.right=process2(list);
        return curNode;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] rootList=data.split(",");
        List<String> list=new ArrayList<>(Arrays.asList(rootList));
        return process2(list);
    }
}

class Offer38{
    List<String> list;
    Map<Character,Integer> map;
    int length;
    public void process(StringBuffer s){
        StringBuffer curString=new StringBuffer(s);
        if (curString.length()==length) {//构成字符串
            list.add(curString.toString());
            return;
        }
        for (char c:map.keySet()){//遍历追加
            int count=map.get(c);
            if (count>0){//该字符可以追加
                curString.append(c);
                map.put(c,count-1);
                process(curString);//追加完成后进入下一层
                curString.deleteCharAt(curString.length()-1);//撤销追加
                map.put(c,count);
            }
        }
    }
    public String[] permutation(String s) {
        list=new ArrayList<>();
        map=new HashMap<>();
        this.length=s.length();
        char[] str=s.toCharArray();
        for (char c:str) {//统计各个字符个数
            if (!map.containsKey(c)) map.put(c,1);
            else map.put(c,map.get(c)+1);
        }
        StringBuffer string=new StringBuffer();
        process(string);
        String[] result=new String[list.size()];
        for (int i=0;i<list.size();i++){
            result[i]=list.get(i);
        }
        System.out.println(list);
        return result;
    }
}